import java.util.ArrayList;

public class SumsOfPerfectPowers {

	// ArrayList<ArrayList<Long>> matrix = new ArrayList<ArrayList<Long>>();
	// static ArrayList<Boolean> result = new ArrayList<Boolean>(5000001);
	ArrayList<Long> numList = new ArrayList<Long>(5000001);
	boolean[] result = new boolean[5000001];

	public SumsOfPerfectPowers() {
		numList.add((long) 0);
		numList.add((long) 1);
		for (int i = 2; i <= 2237; i++) {
			int j = 2;
			double value;
			while ((value = Math.pow(i, j)) <= 5000000) {
				numList.add((long) value);
				j++;
			}
		}

		int len = numList.size();
//		System.out.println(len);
		int value;
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				value = (int) (numList.get(i) + numList.get(j));
				if (value <= 5000001) {
					result[value] = true;
				}
			}
		}

	//	System.out.println("hi");
	}

	static {
	}

	public int howMany(int a, int b) {
		int sum = 0;
		for(int i=a;i<=b;i++) {
			if(result[i]) {
				sum ++;
			}
		}
		return sum;
	}

	public static void main(String[] args) {
//		System.out.println(Math.sqrt(5000000));
		SumsOfPerfectPowers test = new SumsOfPerfectPowers();
		// int i = 5000001;
		// System.out.println(i);
		// System.out.println(StrictMath.pow(27, 1.0/10));
		
		System.out.println(test.howMany(0, 1));
		System.out.println(test.howMany(5, 6));
		System.out.println(test.howMany(25, 30));
		System.out.println(test.howMany(103, 103));
		System.out.println(test.howMany(1, 100000));

	}

}
